IA. Field of the Invention
The present invention is related to segmented compaction of vectors for testing sequential circuits using pruning and critical fault elimination. The present invention is embodied in methods for segmented compaction of vectors; in a system for compacting test vectors and a computer program product enabling a computer to perform segmented compaction.
IB. Background of the Invention
Circuits are tested using test sets comprising test vectors. During testing, a tester applies the test vectors in the test set to the circuit. The outputs generated by the circuit are studied to determine if certain faults exist in the circuit. As can be readily seen, the cost of testing sequential circuits is directly proportional to the number of test vectors in the test set. This is because, more the number of test vectors more is the cost of testing in terms of time and resources required. Therefore, short test sequences are desirable. Reduction in test set size can be achieved using static or dynamic test set compaction algorithms.
Several static compaction approaches for sequential circuits have been proposed. See T. M. Niermann, R. K. Roy, J. H. Patel, and J. A. Abraham, xe2x80x9cTest compaction for sequential circuits,xe2x80x9d IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-267, February 1992, B. So, xe2x80x9cTime-efficient automatic test pattern generation system,xe2x80x9d Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994; I. Pomeranz and S. M. Reddy, xe2x80x9cOn static compaction of test sequences for synchronous sequential circuits,xe2x80x9d Proc. Design Automation Conf, pp. 215-220, Jun. 1996; M. S. Hsiao, E. M. Rudnick, and J. H. Patel, xe2x80x9cFast algorithms for static compaction of sequential circuit test vectors,xe2x80x9d Proc. IEEE VLSI Test Symp., pp. 188-195, April 1995; M. S. Hsiao and S. T. Chakradhar, xe2x80x9cState relaxation based subsequence removal for fast static compaction in sequential circuitsxe2x80x9d, in Proceedings, Design, Automation and Test in Europe (DATE), February, 1998; and R. Guo, I. Pomeranz and S. M. Reddy, xe2x80x9cProcedures for static compaction of test sequences for synchronous sequential circuits based on vector restorationxe2x80x9d, in Proceedings, Design, Automation and Test in Europe (DATE), February, 1998.
Some of these approaches cannot reduce test sets produced by random or simulation-based test generators. The reasons for this can be found in T. M. Niermann, R. K. Roy, J. H. Patel, and J. A. Abraham, xe2x80x9cTest compaction for sequential circuits,xe2x80x9d IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-267, February 1992; and B. So, xe2x80x9cTime-efficient automatic test pattern generation system,xe2x80x9d Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994.
Static compaction techniques based on vector insertion, omission, and selection have already been investigated. For details, see I. Pomeranz and S. M. Reddy, xe2x80x9cOn static compaction of test sequences for synchronous sequential circuits,xe2x80x9d Proc. Design Automation Conf, pp. 215-220, June 1996. The above mentioned static compaction techniques require multiple fault simulation passes. If a vector is omitted or swapped, the fault simulator is invoked. This is done to ensure that the fault coverage is not affected. Fault coverage is the number of faults detected by a specific test set. Though the above mentioned static compaction techniques produce very good compaction, they are computationally intensive.
Vector restoration techniques are aimed at restoring sufficient vectors necessary to detect all faults, starting with the harder faults. Fast static test set compaction based on removing recurring subsequences that start and end on the same states has also been reported recently. For details, see R. Guo, I. Pomeranz and S. M. Reddy, xe2x80x9cProcedures for static compaction of test sequences for synchronous sequential circuits based on vector restorationxe2x80x9d, in Proceedings, Design, Automation and Test in Europe (DATE), February, 1998 and M. S. Hsiao, E. M. Rudnick, and J. H. Patel, xe2x80x9cFast algorithms for static compaction of sequential circuit test vectors,xe2x80x9d Proc. IEEE VLSI Test Symp., pp. 188-195, April 1995. However, these test sets are not as compact as those achieved by algorithms that use multiple fault simulation passes. Recently, compaction based on vector reordering has also been proposed. For details, see M. S. Hsiao and S. T. Chakradhar, xe2x80x9cState relaxation based subsequence removal for fast static compaction in sequential circuitsxe2x80x9d, in Proceedings, Design, Automation and Test in Europe (DATE), February, 1998. However, run-times using the vector reordering approach for large industrial designs are prohibitive.
Dynamic techniques perform compaction concurrently with the test generation process. Details on dynamic compaction techniques can be found in I. Pomeranz and S. M. Reddy, xe2x80x9cDynamic Test Compaction for Synchronous Sequential Circuits using Static Compaction Techniques,xe2x80x9d in Proc. Fault-Tolerant Computing Symp., pp. 53-61, June 1996; S. T. Chakradhar and A. Raghunathan, xe2x80x9cBottleneck removal algorithm for dynamic compaction in sequential circuits,xe2x80x9d IEEE Trans. on Computer-Aided Design, (Accepted for publication) 1997, E. M. Rudnick and Janak H. Patel xe2x80x9cSimulation-based techniques for dynamic test sequence compaction,xe2x80x9d Proc. Intl. Conf. Computer-Aided Design, pp. 67-73, November 1996; and T. J. Lambert and K. K. Saluja, xe2x80x9cMethods for Dynamic Test Vector Compaction in Sequential Test Generation,xe2x80x9d in Proc. Int. Conf. on VLSI Design, pp. 166-169, January 1996. However, these dynamic testing techniques often require modification of the test generator.
Static compaction techniques, on the other hand, are employed after the test generation process. Therefore, they are independent of the test generation algorithm and do not require modifications to the test generator. In addition, static compaction techniques can further reduce the size of test sets obtained after dynamic compaction.
Significant progress has been made in static compaction of test sets for sequential circuits. Static compaction methods have been discussed in detail in S. K. Bommu and S. I Chakradhar and K. B. Doreswamy, xe2x80x9cVector Restoration using Accelerated Validation and Refinementxe2x80x9d, in Proceedings, Asian Test Symposium, December, 1998; R. Guo, 1. Pomeranz and S. M. Reddy, xe2x80x9cProcedures for static compaction of test sequences for synchronous sequential circuits based on vector restorationxe2x80x9d, in Proceedings, Design, Automation and Test in Europe (DATE), February, 1998; S. K. Bommu and S. T. Chakradhar and K. B. Doreswamy, xe2x80x9cStatic test sequence compaction based on segment reordering and fast vector restorationxe2x80x9d, in Proceedings, International Test Conference, October, 1998; and S. K. Bommu and S. T. Chakradhar and K. B. Doreswamy, xe2x80x9cStatic compaction using overlapped restoration and segment pruningxe2x80x9d, in Proceedings, International Conference on Computer Aided Design, November, 1998.
However, better techniques are required to further improve the speed and quality of test set compaction.
Known static compaction algorithms typically compact a given test vector set so that the fault coverage is preserved. The test set is fault graded for a specific defect model (for example, stuck-at faults) to determine the fault coverage. During compaction, the chosen defect model is used to grade the compacted vector set. The present invention is a new approach for compacting vector sets for large production designs. The present invention approach is based at least on the following key observations:
(1) Test sets for production circuits safeguard against a variety of physical defects. Since all defects cannot be covered using a single defect model, test sets include tests generated using multiple defect models like stuck-at, delay, or bridging fault models. Therefore, it is unlikely that a marginal drop in fault coverage during compaction of tests generated for a single defect model will adversely affect the test quality of the overall test set.
(2) Fault coverage is an aggregate measure that can be preserved as long as the original and compacted test sets detect the same number of faults. The specific faults detected by the two test sets can be significantly different. In particular, the compacted vector set may detect new faults that are not detected by the original vector set.
In order to solve the problems mentioned in the background section, an object of the present invention is to provide a method, system and a computer program product for compacting a test set so that the fault coverage of the compacted test set either (1) equals or exceeds the fault coverage of the original test set, or (2) in cases where the coverage of the compacted set is lower than the original test set, the drop in fault coverage is within a pre-specified tolerance limit.
The pre-specified tolerance limit is translated into the maximum number of faults that can be ignored during compaction. These faults constitute the initial resources that can be expended during compaction. Other types of resource constraints are also within the scope of the present invention. The compaction process can be constrained to expend only a pre-specified number of CPU seconds.
Another object of the present invention is to establish that the number of faults allowed to be dropped while constructing a segment, is proportional to the size of the segment under construction.
In order to achieve the objects of the present invention, there is provided a method of generating a vector set, said vector set being used for testing sequential circuits, said method comprising: selecting a plurality of fault models; identifying a fault list each for each of said plurality of fault models; identifying a vector set each for each of said fault lists; selecting a tolerance limit each for each of said fault lists, thereby each fault model having an associated fault list, an associated vector set and an associated tolerance limit; compacting each of said vector set such that the compacted vector set identifies all the faults in the associated fault list or a drop in fault list coverage is within the associated tolerance limit; and creating a vector set by combining all vector sets compacted.
Preferably at least one of said tolerance limits is based on computational resources.
Preferably at least one of said tolerance limits is based on a number of faults dropped from coverage.
Preferably at least one of said tolerance limits is based on power usage.
Preferably at least one of said tolerance limits is based on heat dissipation.
Preferably faults are dropped while a segment is constructed and a number of faults dropped is proportional to a size of the segment.
Preferably said compaction comprises multiple iterations and each of said tolerance limits being dynamic and can be changed for at least one of said multiple iterations, wherein at least one of said tolerance limits can be zero.
Still preferably, said computational resource is CPU usage.
Still preferably said computational resource is memory usage.
Another aspect of the present invention is a method of generating a test vector set, said test vector set being used for testing a sequential circuit, said method comprising: specifying a fault coverage; identifying a list of faults that are covered and a list of faults that are not covered; compacting said vector set so that fault coverage after compaction is at least as large as fault coverage specified, wherein during each iteration of compaction, faults may be exchanged between said list of faults that are covered and said list of faults that are not covered.
Another aspect of the present invention is a system for testing VLSI circuits comprising a test generator, the test generator further comprising: fault model selector for selecting a plurality of fault models, a fault list identifier for identifying a fault list each for each of said plurality of fault models, a vector set identifier for identifying a vector set each for each of said fault lists, a tolerance limit selector for selecting a tolerance limit each for each of said fault lists, thereby each fault model having an associated fault list, an associated vector set and an associated tolerance limit, a dropped-fault compactor for compacting each of said vector set such that the compacted vector set identifies all the faults in the associated fault list or a drop in fault list coverage is within the associated tolerance limit and a vector set creator for combining all compacted vector sets.
Preferably in the testing system at least one of said tolerance limits is based on computational resources.
Preferably in the testing system at least one of said tolerance limits is based on a number of faults dropped from coverage.
Preferably in the testing system at least one of said tolerance limits is based on power usage.
Preferably in the testing system at least one of said tolerance limits is based on heat dissipation.
Preferably in the testing system faults are dropped while a segment is constructed and a number of faults dropped is proportional to a size of the segment.
Still preferably in the testing system the computational resource is CPU usage.
Still preferably in the testing system said computational resource is memory usage.
Another aspect of the present invention is a computer program product including a computer-readable media comprising computer code that enables a VLSI tester to test VLSI circuits, said computer code comprising: a fault model selector code for enabling a computer to select a plurality of fault models, a fault list identifier code for enabling a computer to identify a fault list each for each of said plurality of fault models, a vector set identifier code for enabling a computer to identify a vector set each for each of said fault lists, a tolerance limit code selector enabling a computer to select a tolerance limit each for each of said fault lists, thereby each fault model having an associated fault list, an associated vector set and an associated tolerance limit, a dropped-fault compactor code for enabling a computer to compact each of said vector set such that the compacted vector set identifies all the faults in the associated fault list or a drop in fault list coverage is within the associated tolerance limit; and a vector set creator code for enabling a computer to combine all compacted vector sets.
Preferably in the computer program product at least one of said tolerance limits is based on computational resources.
Preferably in the computer program product at least one of said tolerance limits is based on a number of faults dropped from coverage.
Preferably in the computer program product at least one of said tolerance limits is based on power usage.
Preferably in the computer program product at least one of said tolerance limits is based on heat dissipation.
Preferably in the computer program product faults are dropped while a segment is constructed and a number of faults dropped is proportional to a size of the segment.
Still preferably in the computer program product said computational resource is CPU usage.
Preferably in the computer program product said computational resource is memory usage.